A networking switch receives data packets from a number of ingress ports connected to the switch and forwards the data packets to one or more egress ports connected to the switch. The switch determines the egress port to which the data packets are forwarded dependent on a destination address and other fields included in the data packet.
The data packet received at an ingress port includes network protocols encoded in one or more headers included in the data packet. The headers are a standard length specified by the network protocols.
FIG. 1A illustrates a prior art data packet 100. The data packet includes a physical layer (L1) header 102, a data link layer (L2) header 104, a network layer (L3) header 106 and a transport layer (L4) header. A payload for the data packet is stored in a data field 110 and the data packet 100 also includes a checksum 112.
FIG. 1B illustrates a prior art Ethernet protocol header stored in the data link (L2) header 104 shown in FIG. 1A. The length of the Ethernet protocol header is a fixed number of bits which is specified by the standard Ethernet protocol. The data link (L2) header 104 includes a 6-byte L2 destination address 114, a 12-bit Virtual Local Area Network Identifier (xe2x80x9cVLAN IDxe2x80x9d) 118 and a 2-byte length/type field 120.
The network switch forwards data packets from one Local Area Network (xe2x80x9cLANxe2x80x9d) segment connected to the switch to another LAN segment connected to the switch. The switch determines whether a data packet received from one LAN segment is to be forwarded to another LAN segment. A broadcast data packet received at an ingress port in the switch is forwarded to all members of the LAN and thus consumes a large proportion of the LAN""s bandwidth. In order to reduce the number of broadcast data packets forwarded on a LAN, members of a physical LAN are added to logical groups called Virtual LANs. A broadcast data packet is only forwarded to members of the Virtual LAN from which it originated. The virtual LAN is encoded in the VLAN ID 118 included in the Ethernet protocol header stored in the data link (L2) header 104 in the received data packet.
The 12-bit VLAN ID 118 allows a physical LAN to have up to 212 (4096) VLANS. Typically, not all 212 VLANS are used, but a 12-bit VLAN ID 118 is forwarded in the data link layer (L2) header 104 included in each Ethernet protocol data packet received by the switch. If the switch supports a subset of the 212 VLANS per physical LAN, for example, 28 (256) VLANS, the switch may translate the 12-bits received in the VLAN ID to an 8-bit Internal VID (xe2x80x9cIVIDxe2x80x9d). The use of an 8-bit IVID in the switch reduces the memory required in the switch for forwarding a VLAN ID with each data packet internally in the switch.
The translation of a relatively small number of bits (12-bit VLAN) to a smaller number of bits (8-bit IVID) is typically performed using a lookup table. An example of one such prior art lookup table is shown in FIG. 1C. The prior art lookup table includes an entry for each possible VLAN; that is, 212 (4096) IVID entries. Each IVID entry is eight-bits wide, thus the size of the lookup table is 32K-bits (4096xc3x978). There are a maximum of 28 (256) possible IVID values stored in 256 of the 4096 IVID entries in the lookup table. Thus, the use of a 32K lookup table to translate a 12-bit VLAN ID to an 8-bit IVID consumes more memory than is necessary to store the 256 possible IVID entries by providing a location for each of the 4096 possible VLAN IDs.
An alternative method for translating one number of bits to a smaller number of bits is to use a hash function. A hash function is typically used to convert a large memory space to a small memory space, such as to map a 48-bit (6 bytes) L2 destination address 114 to a smaller number of bits. Hash function logic performs a hash function on the L2 destination address 114 and uses the result of the hash function to search an address space smaller than the 248 entries dependent on the smaller number of bits which is required for the original number of bits.
However, the use of a hashing function to translate a relatively small number (12-bit VLAN ID) to a smaller number (8-bit IVID) does not significantly reduce the memory requirements in order to justify adding the complex logic required to perform the hash function.
We present a multi-stage lookup table for translating a first signal having a first number of bits to a second signal having a second number of bits less than the first number of bits. Portioning logic portions the first number of bits into a portion of bits and a delta subset of bits. The size of the portion of bits is at least the size of the second number of bits. Memory access logic sequentially performs a lookup in each of a plurality of memory elements. The number of memory elements is dependent on the number of delta subsets. The memory access logic performs a first lookup to a first memory element using a first index equal to the portion of bits. The memory access logic performs a next lookup to a next memory element using a next index equal to a combination of a result of the previous lookup and a next delta subset of bits. The second signal results from a last lookup to a last memory element.
Preferably, the number of memory elements is two or four. The size of the memory element is dependent on the size of an index equal to the number of bits in the subset of bits and the number of bits in the delta subset of bits. The width of the memory element is dependent on the number of bits in the second signal.
In one embodiment, the number of memory elements is two and the number of bits in the delta subset is two to provide a 2-stage lookup to translate a first set of 12-bits to a second set of 8.